/**
 * 22. 括号生成
 * https://leetcode-cn.com/problems/generate-parentheses/
 */

const parenthesisLeft = 40;
const parenthesisRight = 41;

/**
 * @param {number[]} stack
 * @param {number} index
 * @param {number} pairCount
 * @param {number} leftCount
 * @param {number} rightCount
 * @param {string[]} total
 */
function generate(stack, index, pairCount, leftCount, rightCount, total) {
  if (index >= stack.length) {
    total.push(String.fromCharCode.apply(null, stack));
    return;
  }
  if (leftCount >= pairCount) {
    // eslint-disable-next-line no-param-reassign
    stack[index] = parenthesisRight;
    generate(stack, index + 1, pairCount, leftCount, rightCount + 1, total);
    return;
  }
  // eslint-disable-next-line no-param-reassign
  stack[index] = parenthesisLeft;
  generate(stack, index + 1, pairCount, leftCount + 1, rightCount, total);
  if (rightCount < leftCount) {
    // eslint-disable-next-line no-param-reassign
    stack[index] = parenthesisRight;
    generate(stack, index + 1, pairCount, leftCount, rightCount + 1, total);
  }
}

/**
 * @param {number} n
 * @return {string[]}
 */
function generateParenthesis(n) {
  const result = [];
  generate(new Array(n * 2), 0, n, 0, 0, result);
  return result;
}

console.log(generateParenthesis(1));
console.log(generateParenthesis(2));
console.log(generateParenthesis(3));
console.log(generateParenthesis(4));
console.log(generateParenthesis(5));
console.log(generateParenthesis(6));
console.log(generateParenthesis(7));
console.log(generateParenthesis(8));
